Search results for " Complexity"
showing 10 items of 623 documents
Exceptional Configurations of Quantum Walks with Grover’s Coin
2016
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation -- Grover's diffusion transformation -- has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by [AR08].
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
Text Compression Using Antidictionaries
1999
International audience; We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. Our algorithms can also be presented as "compilers" that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata.
Complejidad social y calidad informativa: hacia un periodismo "glocal"
2013
In the so-called information (and knowledge) society, quality information is, more than ever, an indispensable and inalienable public good for any citizen who wants to exercise his or her civic and political rights. Because of this, we need to have reliable (rigorous and autonomous) communication media, which disseminate relevant and quality information. But journalism does not only depend on structural questions, but also on the conditions and limits (such as simplification, for instance) that mark professional praxis, either of the political or the socioeconomic type. Social complexity requires a treatment of information that might explain reality, which implies taking advantage of the sc…
Fast Algorithms for Pseudoarboricity
2015
The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time. We discuss algorithms for this problem and the computation of a graph orientation with the lowest maximum indegree, which is equal to ⌈d∗⌉. This value also equals the pseudoarboricity of the graph. We show that it can be computed in O(|E| √ log log d∗) time, and that better estimates can be given for graph classes where d∗ satisfies certain asymptotic bounds. These runtimes are achieved by accelerating a binary search with an approximation scheme, and a runtime analysis of Dinitz’s algorithm on flow networks where all arcs, except the source and sink arcs, hav…
Quantum Online Algorithms with Respect to Space Complexity
2017
Online algorithm is a well-known computational model. We introduce quantum online algorithms and investigate them with respect to a competitive ratio in two points of view: space complexity and advice complexity. We start with exploring a model with restricted memory and show that quantum online algorithms can be better than classical ones (deterministic or randomized) for sublogarithmic space (memory), and they can be better than deterministic online algorithms without restriction for memory. Additionally, we consider polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well.
CUDA-Accelerated Alignment of Subsequences in Streamed Time Series Data
2014
Euclidean Distance (ED) and Dynamic Time Warping (DTW) are cornerstones in the field of time series data mining. Many high-level algorithms like kNN-classification, clustering or anomaly detection make excessive use of these distance measures as subroutines. Furthermore, the vast growth of recorded data produced by automated monitoring systems or integrated sensors establishes the need for efficient implementations. In this paper, we introduce linear memory parallelization schemes for the alignment of a given query Q in a stream of time series data S for both ED and DTW using CUDA-enabled accelerators. The ED parallelization features a log-linear calculation scheme in contrast to the naive …
Networks in biological systems: An investigation of the Gene Ontology as an evolving network
2009
Many biological systems can be described as networks where diFFerent elements interact, in order to perform biological processes. We introduce a network associated with the Gene Ontology. Specifically, we construct a correlation-based network where the vertices are the terms of the Gene Ontology and the link between each two terms is weighted on the basis of the number of genes that they have in common. We analyze a filtered network obtained from the correlation-based network and we characterize its evolution over different releases of the Gene Ontology.
Complexity and interaction: comparing the development of L1 and L2
2011
In research into first and second language development, the focus has mainly been either on the formal features of learner language alone (both L1 and L2) or on the interaction between learners and their caretakers (L1) or native speaker peers (L2).These research traditions have been kept a part even though it has been widely acknowledged that both first and second languages are appropriated essentially in social interaction. This paper aims to strengthen the connection between social and formal approaches by combining interactional views with those focusing on the structural complexity of learner language. Some excerpts from L1 and L2 interaction data (in the Finnish language) are discusse…
Comorbidity does not mean clinical complexity: evidence from the RePoSI register
2019
In the last 2–3 decades internists have confronted dramatic changes in the pattern of patients acutely admitted to hospital wards. Internists observed a shift from younger subjects affected by a single organ disease to more complex patients, usually older, with multiple chronic conditions, attended by different specialists, with poor integration and treated with multiple drugs. In this regard, the concept of complex patients is addressed daily in clinical practice even if there is no agreed definition of patient complexity. To try to evaluate clinical complexity different instruments have been proposed. Among these, the number of comorbidities (NoC) was considered a marker of clinical compl…